#include<vector>
#include<string>
using namespace std;

//bool vis[7][7];
//int m, n;
//int px[4] = { 0, 0, -1, 1 };
//int py[4] = { -1, 1, 0, 0 };
//
//bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos)
//{
//    if (pos == word.size())
//    {
//        return true;
//    }
//    for (int k = 0; k < 4; k++)
//    {
//        int x = i + px[k], y = j + py[k];
//        if (x >= 0 && y >= 0 && x < m && y < n && !vis[x][y] && word[pos] == board[x][y])
//        {
//            vis[i][j] = true;
//            if (dfs(board, x, y, word, pos + 1)) return true;
//            vis[i][j] = false;
//        }
//    }
//    return false;
//}
//bool exist(vector<vector<char>>& board, string word)
//{
//    m = board.size(), n = board[0].size();
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            if (board[i][j] == word[0])
//            {
//                vis[i][j] = true;
//                if (dfs(board, i, j, word, 1)) return true;
//                vis[i][j] = false;
//            }
//        }
//    }
//    return false;
//}

//int px[4] = { 0, 0, -1, 1 };
//int py[4] = { 1, -1, 0, 0 };
//bool vis[16][16];
//int m, n;
//int ret;
//void dfs(vector<vector<int>>& grid, int i, int j, int path)
//{
//    ret = max(ret, path);
//    for (int k = 0; k < 4; k++)
//    {
//        int x = i + px[k], y = j + py[k];
//        if (x >= 0 && y >= 0 && x < m && y < n && grid[x][y] != 0 && !vis[x][y])
//        {
//            vis[x][y] = true;
//            dfs(grid, x, y, path + grid[x][y]);
//            vis[x][y] = false;
//        }
//    }
//}
//int getMaximumGold(vector<vector<int>>& grid) {
//    m = grid.size(), n = grid[0].size();
//
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            if (grid[i][j] != 0)
//            {
//                vis[i][j] = true;
//                dfs(grid, i, j, grid[i][j]);
//                vis[i][j] = false;
//            }
//        }
//    }
//
//    return ret;
//}

int px[4] = { 0, 0, -1, 1 };
int py[4] = { 1, -1, 0, 0 };
bool vis[21][21];
int m, n;
int ret;
int count;

void dfs(vector<vector<int>>& grid, int i, int j, int zero)
{
    if (grid[i][j] == 2)
    {
        if (zero == count) ret++;
        return;
    }
    for (int k = 0; k < 4; k++)
    {
        int x = i + px[k], y = j + py[k];
        if (x >= 0 && y >= 0 && x < m && y < n && !vis[x][y] && grid[x][y] != -1)
        {
            vis[x][y] = true;
            dfs(grid, x, y, zero + 1);
            vis[x][y] = false;
        }
    }
}
int uniquePathsIII(vector<vector<int>>& grid) {
    m = grid.size(), n = grid[0].size();
    int a = 0, b = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == 0) count++;
            else if (grid[i][j] == 1) a = i, b = j;
        }
    }
    vis[a][b] = true;
    dfs(grid, a, b, -1);

    return ret;
}

int main()
{
    vector<vector<int>> v{ {1,0,0,0 }, { 0,0,0,0 }, { 0,0,2,-1 } };
    uniquePathsIII(v);

	return 0;
}